#include "../tools.h"


class Solution {
public:
    int qsearch(vector<int>& nums, int left, int right, int k){
        if(left == right) return nums[left];

        int base = left;
        int p1 = left + 1, p2 = right;
        while(p1 < p2){
            while(p1 < p2 && nums[base] <= nums[p2]) --p2;
            while(p1 < p2 && nums[p1] <= nums[base]) ++p1;
            if(p1 < p2) swap(nums[p1], nums[p2]);
        }
        if(nums[p1] < nums[base]){
            swap(nums[p1], nums[base]);
            base = p1;
        }
        if(base == k) return nums[base];
        else if(base < k) return qsearch(nums, base + 1, right, k);
        else return qsearch(nums, left, base - 1, k);

    }
    int findKthLargest(vector<int>& nums, int k) {
        int right = nums.size() - 1;
        return qsearch(nums, 0, right, right - k + 1);
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    // vector<int> nums = {7,6,5,4,3,2,1};
    // int k = 2;
    vector<int> nums = {3,2,3,1,2,4,5,5,6};
    int k = 4;
    
    cout << sol.findKthLargest(nums, k);

    return 0;
}
